// https://www.lintcode.com/problem/regular-expression-matching/description

class Solution {
public:
    /**
     * @param s: A string 
     * @param p: A string includes "." and "*"
     * @return: A boolean
     */
    // bool isMatch(string s, string p) {
    //     if (s.length() == 0){
    //         // s串匹配完合法的情况只有p为空，或是 "X*X*"的形式
    //         if (p.length() & 1) return false;  //不满足"X*X*"的形式
    //         else {
    //             for (int i = 1; i < p.length(); i += 2) {
    //                 if (p[i] != '*') return false;   //如果不是'*',不满足"X*X*"的形式
    //             }
    //         }
    //         return true;
    //     }
    //     if (p.length() == 0) return false;
    //     if (p.length() > 1 && p[1] == '*') {
    //         if (p[0] == '.' || s[0] == p[0]) {   //第0位匹配成功
    //             return isMatch(s.substr(1), p) || isMatch(s, p.substr(2)); //对于'*'，存在两种选择，'*'不进行匹配，或者匹配s的下一个
    //         } else return isMatch(s, p.substr(2));   //s没有匹配成功，继续拿p的下一位匹配
    //     } else {
    //         if (p[0] == '.' || s[0] == p[0]) {    		//如果第0位置匹配成功
    //             return isMatch(s.substr(1), p.substr(1));		//继续匹配下一位
    //         } else return false;
    //     }
    // }
    
    bool isMatch(string s, string p) {
        int m = s.length();
        int n = p.length();
        vector<vector<bool>> rec(m + 1, vector<bool>(n + 1));
        rec[0][0] = true;
        for (int i = 1; i < m; ++i)
        {
            rec[i][0] = false;
        }
     
        for (int i = 0; i < m + 1; ++i)
        {
            for (int j = 1; j < n + 1; ++j)
            {
                // 1.最后是单个字符相等
                // 2.最后是c*：1) 0个c 2) 多个c
                if (p[j - 1] != '*')
                {
                    if (i > 0 && (p[j - 1] == s[i - 1] || p[j - 1] == '.'))
                    {
                        rec[i][j] = rec[i - 1][j - 1];
                    }
                }
                else
                {
                    if (j > 1)
                    {
                        rec[i][j] = rec[i][j - 2];
                    }
                    if (i > 0 && j > 1 && (p[j - 2] == s[i - 1] || p[j - 2] == '.'))
                    {
                        rec[i][j] = rec[i][j] || rec[i - 1][j];
                    }
                }
            }
        }
        return rec[m][n];
    }
};